package algorithms.a06unionfind;

import com.google.common.base.Preconditions;

/**
 * 并查集 第4版
 * 基于rank的优化，建议使用的方式，
 *
 * @author 王昊然
 * @create 2018-02-23 9:13
 **/
public class UnionFind4 {

    private int[] parents;
    private int count;
    private int[] ranks;//ranks[i]指以i为根，对应这棵树的层数

    public UnionFind4(int n) {
        parents = new int[n];
        count = n;
        ranks = new int[n];

        for (int i = 0; i < n; i++) {
            parents[i] = i;
            ranks[i] = 1;
        }
    }

    /**
     * 查找p对应的根
     * p是元素下标
     *
     * @param p
     * @return
     */
    public int find(int p) {
        Preconditions.checkArgument(p < count, "p超出集合范围");

        while (p != parents[p]) {//如果一个下标的parent值是下标值，那么这是一个根节点
            p = parents[p];
        }
        return p;
    }

    public boolean isConnected(int p, int q) {

        return find(p) == find(q);
    }

    public void unionElements(int p, int q) {

        int rootp = find(p);
        int rootq = find(q);

        if (rootp == rootq) return;

        if (ranks[rootp] < ranks[rootq]) {
            parents[rootp] = rootq;
        } else if (ranks[rootp] > ranks[rootq]) {
            parents[rootq] = rootp;
        } else{//ranks[rootp] == ranks[rootq]
            parents[rootq] = rootp;//谁指向谁无所谓
            ranks[rootp] += 1;
        }
    }

    // 测试UF1
    public static void main(String[] args){

        // 使用10000的数据规模
        int n = 1000000;

        // 虽然isConnected只需要O(1)的时间, 但由于union操作需要O(n)的时间
        // 总体测试过程的算法复杂度是O(n^2)的
        //UnionFindTestHelper.testUF1(n);
        //UnionFindTestHelper.testUF2(n);
        UnionFindTestHelper.testUF3(n);
        UnionFindTestHelper.testUF4(n);

        //从测试结果看，3 不一定优于4，但是差别不大，并且4对一些极端情况有优势，所以讲师建议使用4方式
    }
}
